This disclosure relates generally to a method and system for production/manufacturing planning and scheduling. More specifically the disclosure relates to the on-line state-space planning of operations for manufacturing or production tasks.
Manufacturing systems conventionally require the planning and scheduling of a series of jobs. Because execution of plans requires the use of physical plant resources, planning for later jobs must take into account the resource commitments in plans already released for production. For example, if part 1 is scheduled to use machine 2 for 15 seconds starting at 4:00:00 pm, the plan for part 2 cannot use machine 2 from 4:00:00 to 4:00:15 pm. While production planning and scheduling may be simple for systems that manufacture many identical jobs in an assembly-line fashion, or factories that produce a very small number of custom jobs over a long period of time, it can be extremely difficult in situations involving high-speed custom made-to-order manufacturing, in which different objects may require different processing and the production plan for an object must be created very quickly.
A typical manufacturing plant may be represented as a network of transports linking multiple machines, as shown in FIG. 1. A plant may have anywhere from a few to a several hundred machines and transports. Unfinished blocks of raw material may enter the plant from multiple sources and completed jobs can exit at multiple destinations. In the simplified schematic of FIG. 1, sources 1 and 2 provide materials to Machine 1 and Machine 2, which interface with Machine 3 and Machine 4 as well as Destinations 1 and 2. Transports between sources, machines, and destinations take a known time to convey jobs. Each machine has a limited number of discrete actions it can perform, each of which has a known duration and transforms its input in a known deterministic way.
From a planning perspective, jobs can move through the plant as illustrated in FIG. 2. A job request specifies a desired final configuration, which may be achievable by several different sequences of actions. For example, in FIG. 2 material may be procured from source S1 to be received and processed by machine M1 utilizing either a first or second operation Act1 or Act2. At the completion of either Act1 or Act2, materials may be sent to destination D1, to machine M3, or to machine M2 for further processing. The plant might operate at high speed, with multiple job requests arriving per second, possibly for many hours. Clearly, a fast, automated procedure is necessary to coordinate production, and one that optimizes the throughput of the plant would be advantageous.
Furthermore, additional scheduling constraints may be present. In many situations of interest, jobs are grouped into batches. A batch is an ordered set of jobs, all of which must eventually arrive in order at the same destination. Multiple batches may be in production simultaneously, although because jobs from different batches are not allowed to interleave at a single destination, the number of concurrent batches is limited by the number of destinations.
Occasionally a machine or transport will break down, in effect changing the planning domain by removing the related actions. The plant is also intentionally reconfigured periodically. This means that precomputing a limited set of canonical suboptimal plans and limiting on-line computation to scheduling only is not desirable. For a large plant of 200 machines, there are infeasibly many possible broken configurations to consider. Depending on the capabilities of the machines, the number of possible job requests may also make precomputation infeasible.
The planner must accept a stream of job specifications that arrive asynchronously over time and produce a plan for each job. Each plan is a sequence of actions labeled with start times. The plant controller executes the plans it is given and reports any failures. Due to communication and processing delays, any plan that is returned by the planner must start later than a certain time past the current instant.
Typically there are many feasible plans for any given job request; the problem is finding one that finishes quickly. The optimal plan for a job depends not only on the job request, but also on the resource commitments present in previously-planned jobs. Existing approaches to this problem require the enumeration of all possible plans at machine start-up, with retrieval of a suitable plan for each job request and then scheduling of the necessary actions. However, the large number of potential plans in more complex plants makes an on-line planning system desirable.